﻿//给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
//现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。
//我们用这种形式来构造 数对链 。
//找出并返回能够形成的 最长数对链的长度 。
//你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
//
//输入：pairs = [[1, 2], [2, 3], [3, 4]]
//输出：2
//解释：最长的数对链是[1, 2] ->[3, 4] 。
//
//输入：pairs = [[1, 2], [7, 8], [4, 5]]
//输出：3
//解释：最长的数对链是[1, 2] ->[4, 5] ->[7, 8] 。
//
//提示：
//	n == pairs.length
//	1 <= n <= 1000
//	- 1000 <= lefti < righti <= 1000

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end()); // 排序
        int n = pairs.size();
        vector<int> dp(n, 1); // 创建 dp数组，顺便初始化
        int ret = 1;          // 记录最⼤值
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 找出所有情况下的最⼤值
                if (pairs[j][1] < pairs[i][0])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]); // 更新最⼤值
        }
        return dp[n - 1];
    }
};
